package com.zjsru.oneDay202203;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @Author: likew
 * @Date: 2022/3/20
 *
 * 网络空闲的时刻
 *
 * 输入：edges = [[0,1],[1,2]], patience = [0,2,1]
 * 输出：8
 * 解释：
 * 0 秒最开始时，
 * - 数据服务器 1 给主服务器发出信息（用 1A 表示）。
 * - 数据服务器 2 给主服务器发出信息（用 2A 表示）。
 *
 * 1 秒时，
 * - 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
 * - 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
 * - 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。
 *
 * 2 秒时，
 * - 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
 * - 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
 * - 服务器 2 重发一条信息（用 2C 表示）。
 * ...
 * 4 秒时，
 * - 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
 * ...
 * 7 秒时，回复信息 2D 到达服务器 2 。
 *
 * 从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
 * 所以第 8 秒是网络变空闲的最早时刻。
 *
 */
public class networkBecomesIdle {
    static int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] dist = new int[N];
    int idx;
    void add(int a,int b){
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(he,-1);
        Arrays.fill(dist,INF);
        int n = patience.length;
        for (int[] e: edges) {
            add(e[0],e[1]);
            add(e[1],e[0]);
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(0);
        dist[0] = 0;
        while(!deque.isEmpty()){
            int t = deque.pollFirst();
            for (int i = he[t]; i != -1; i=ne[i]) {
                int j = e[i];
                if(dist[j] != INF){
                    continue;
                }
                dist[j] = dist[t]+1;
                deque.addLast(j);
            }
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
          int di =dist[i]*2,t=patience[i];
          int cur = di <= t ? di: (di -1)/t*t+di;
          if(cur >ans) ans = cur;
         }
        return ans +1;
    }
    
    public static void main(String[] args) {
        networkBecomesIdle networkBecomesIdle = new networkBecomesIdle();
        int[][] edges =new int[][]{{0,1},{1,2}};
        int[] patience = new int[]{0,2,1};
        System.out.println(networkBecomesIdle.networkBecomesIdle(edges, patience));
    }
}
